package com.shuang.dp10;

class Solution {
    //将数组中的石头分成两堆尽可能相似的重量 这样相撞后剩余的重量是最小的
    //转化为01背包问题 容量为sum/2 最大价值也是石头的最大重量 也是sum/2
    public int lastStoneWeightII(int[] stones) {
        //石头数组求和
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }

        //dp[j] 表示容量为j的背包 所装的最大价值（最大石头重量）d[j]
        int n = sum / 2;
        int[] dp = new int[n + 1];

        //递归

        //初始化

        //遍历
        for (int i = 0; i < stones.length; i++) {
            for (int j = n; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        //计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的
        //那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]
        int res = sum - dp[n] - dp[n];

        return res;
    }
}